package listbyorder.access001_100.test87;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/5 10:15
 */
public class Solution3 {

    // 方法三————动态规划=========时间成本上并没有赶上暴力递归
    // dp数组的含义： dp[i][j][k] ------- 标识从s1的第j个字符开始，s2的第k个字符开始，向后遍历i个位置之后，s1和s2当前的字符是否可以匹配
    public boolean isScramble4(String s1, String s2) {
        if (s1.equals(s2)) return true;
        if (s1.length() != s2.length()) return false;

        int len = s1.length();
        // 创建dp数组
        boolean[][][] dp = new boolean[len + 1][len][len];
        // 遍历数组
        for (int i = 1; i <= len; i++) {
            for (int j = 0; j + i <= len; j++) {
                for (int k = 0; k + i <= len; k++) {
                    // 首先如果当前的长度是1的时候
                    if (i == 1) {
                        dp[i][j][k] = s1.charAt(j) == s2.charAt(k);
                    } else {
                        // 从1开始将当前的长度进行切分
                        for (int p = 1; p < i; p++) {
                            dp[i][j][k] = (dp[p][j][k] && dp[i - p][j + p][k + p]) || (dp[p][j][k + i - p] && dp[i - p][j + p][k]);
                            if (dp[i][j][k]) {
                                break;  // 结束当前的循环
                            }
                        }
                    }
                }
            }
        }
        return dp[len][0][0];
    }
}
